package src.dynamic_programming;

/**
 * @author starsea
 * @date 2024-09-18 15:35
 */

public class Test18 {
    public static void main(String[] args) {
        String text1 = "abcde";
        String text2 = "ace";
        int c=longestCommonSubsequence(text1,text2);
    }
    public static int longestCommonSubsequence(String text1, String text2) {
        text1=" "+text1;
        text2=" "+text2;
        int n=text1.length();
        int m=text2.length();
        int[][] dp=new int[m][n];
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                if(text1.charAt(j)==text2.charAt(i))
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
            }
        }
        return dp[m-1][n-1];
    }
}
